package org.algorithm.二师兄.数组.二月;

import java.util.Arrays;

/**
 * @author 二师兄
 * @version 1.0
 * @date 2022/03/06 9:07 PM   星期二的作业
 * @description:
 * <p>
 *     数组中四数相加最接近target
 *     输入：nums = [-1,2,1,-4], target = 1
 *     输出：2
 *     解释：与 target 最接近的和是 2 (-1 + 2 + 1 + 0 = 2) 。
 * </p>
 *
 * uri: 没有,  如果有， 请参考   最接近的三数之和
 */
public class 最接近的四数之和 {

    public static void main(String[] args) {
        int[] nums = {-1,2,1,-4,5,3,0,-2};
        System.out.println(fourSumClosest(nums, 1));
    }

    // 抄最接近的三数之和
    public static int fourSumClosest(int[] nums, int target) {
        if (nums == null || nums.length < 4) return 0;
        // 排序是为了方便双指针
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int right = nums.length - 1;
            int ans = nums[0] + nums[1] + nums[2] + nums[3];
            for (int j = i + 1; j < nums.length; j++) {
                int left = j + 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (Math.abs(target - sum) < Math.abs(target - ans)) {
                        ans = sum;
                    }
                    if (sum > target) {
                        right--;
                    }else if (sum < target) {
                        left++;
                    }else {
                        return ans;
                    }
                }
            }
            return ans;
        }
        return -1;
    }
}
